/**
 * 1754. 构造字典序最大的合并字符串
 * https://leetcode-cn.com/problems/largest-merge-of-two-strings/
 */
public class Solutions_1754 {
    public static void main(String[] args) {
//        String word1 = "cabaa", word2 = "bcaaa";  // output: "cbcabaaaaa"
//        String word1 = "abcabc", word2 = "abdcaba";  // output: "abdcabcabcaba"
        String word1 = "abc", word2 = "abca";  // output: ""
//        String word1 = "guguuuuuuuuuuuuuuguguuuuguug";
//        String word2 = "gguggggggguuggguugggggg";
        // output: "guguuuuuuuuuuuuuuguguuuuguugguggggggguuggguuggggggg"

        String result = largestMerge(word1, word2);
        System.out.println(result);
    }

    /**
     * 解题思路：贪心法
     * 关键：若前面的字符相同，还需要根据后续字符来进行判断
     * 以字符串 abcabc、abdcaba 为例：
     * 1. 第 1 个字符相同，则判断第 2 个字符
     * 2. 第 2 个字符相同，则判断第 3 个字符
     * 3. 第 3 个字符中，字符 d > c，故选择 abd 中的 a 字符
     */
    public static String largestMerge(String word1, String word2) {
        int idx1 = 0, idx2 = 0;
        char[] arr1 = word1.toCharArray();
        char[] arr2 = word2.toCharArray();
        char[] res = new char[arr1.length + arr2.length];
        int i = 0;

        while (idx1 < arr1.length && idx2 < arr2.length) {
            if (arr1[idx1] > arr2[idx2]) {
                res[i] = arr1[idx1];
                idx1 ++;
            } else if (arr2[idx2] > arr1[idx1]) {
                res[i] = arr2[idx2];
                idx2 ++;
            } else {
                // 相等的情况，需要判断
                // flag = true，取 arr1 中的字符，否则取 arr2 中的字符
                boolean flag = helper(arr1, idx1 + 1, arr2, idx2 + 1);
                if (flag) {
                    res[i] = arr1[idx1];
                    idx1 ++;
                } else {
                    res[i] = arr2[idx2];
                    idx2 ++;
                }
            }
            i ++;
        }
        // word1 字符串中还有元素未添加到 res 中
        while (idx1 < arr1.length) {
            res[i] = arr1[idx1];
            idx1 ++;
            i ++;
        }
        // word2 字符串中还有元素未添加到 res 中
        while (idx2 < arr2.length) {
            res[i] = arr2[idx2];
            idx2 ++;
            i ++;
        }
        return String.valueOf(res);
    }

    public static boolean helper(char[] arr1, int idx1, char[] arr2, int idx2) {
        while (idx1 < arr1.length && idx2 < arr2.length && arr1[idx1] == arr2[idx2]) {
            idx1 ++;
            idx2 ++;
        }
        if (idx1 == arr1.length) {
            return false;
        }
        if (idx2 == arr2.length) {
            return true;
        }
        return arr1[idx1] > arr2[idx2];
    }
}
